package com.example;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.FutureTask;

/**
 * @Author loubobooo
 * @Description #3. 无重复字符的最长子串
 * @Date 2019/9/3
 */
public class LongestSubstringWithoutRepeatingCharacters {
    /**
     * @return
     * @Author loubobooo
     * @Description 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     * @Date 2019/9/3 15:19
     * @Param
     **/
    public int lengthOfLongestSubstring(String s) {
        // 此题展现出来的维度有三个。思路是先降维，将买、卖、冷冻，降维成两个维度：持有股票和未持有股票。
        // 持有股票：今天买入和之前买入但未卖出
        // 未持有：今天卖出和冷冻期 所以有的传递式：
        // hold[i]=max(hold[i-1],notHold[i-2]-prices[i]); 意思是当前持有的股票的最大收益是昨天持有的股票
        // （可能今天并未有任何操作）和之前卖出的最大收益-今天买入的(i-2的意思是今天买入的话，昨天就应该是冷冻期)。
        //
        // notHold[i]=max(notHold[i-1],hold[i-1]+prices[i]);最大收益的就很容易理解。
        //
        //用此思路也可以解决上一个最佳买卖股票题型。可能我们都能直到这题的解决方法，难点就在于如何找到解决公式
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int length = s.length();
        int left = 0;
        int right = 0;
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();

        while(right < length){
            if(map.containsKey(s.charAt(right))){
                left = Math.max(left, map.get(s.charAt(right)) + 1);
            }
            map.put(s.charAt(right), right);
            max = Math.max(max, right - left + 1);
            right++;
        }
        return max;
    }

    public static void main(String[] args) {
        LongestSubstringWithoutRepeatingCharacters longest = new LongestSubstringWithoutRepeatingCharacters();
        int length = longest.lengthOfLongestSubstring("pwwkew");
        System.out.println(length);
    }

}
